package org.example.algo;

import java.util.Arrays;

/**
 * 局部最小值
 * 1. 数组无序, 相邻两个数不相等
 * @author shenguangyang
 */
public class N04_LocalMin {
    public static void main(String[] args) {
        for (int i = 0; i < 10000; i++) {
            int[] arr = randomArr(100,10000);
            int localMinIndex = localMin(arr);
            if (!check(arr, localMinIndex)) {
                System.err.println("not find: " + Arrays.toString(arr));
            }
            System.out.println("check " + i);
        }

    }

    public static int[] randomArr(int maxLen, int maxValue) {
        int len = (int) (Math.random() * maxLen);
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            do {
                int value = (int) (Math.random() * maxValue);
                arr[i] = value;
            } while (i > 0 && arr[i - 1] == arr[i]);
        }
        return arr;
    }

    public static boolean check(int[] arr, int localMinIndex) {
        try {
            if (arr == null || arr.length <= 1 || localMinIndex == -1) {
                return false;
            }
            int left = localMinIndex - 1;
            int right = localMinIndex + 1;
            boolean leftBigger = left < 0 || arr[left] > arr[localMinIndex];
            boolean rightBigger = right >= arr.length || arr[right] > arr[localMinIndex];

            if (leftBigger && rightBigger) {
                return true;
            } else {
                System.out.println("localMinIndex: " + localMinIndex);
                System.out.println("arr:           " + Arrays.toString(arr));
                return false;
            }
        } catch (Exception e) {
            System.err.println("localMinIndex: " + localMinIndex);
            System.err.println("arr:           " + Arrays.toString(arr));
            throw new RuntimeException(e);
        }
    }

    public static int localMin(int[] arr) {
        if (arr == null || arr.length < 2) {
            return -1;
        }

        int n = arr.length;

        // 第一个元素如果比第二个要小，因为左边没有数，所以第一个元素就是一个局部最小数。
        if (arr[0] < arr[1]) {
            return 0;
        }
        // 数组最后一个元素如果比倒数第二个元素值要小，说明最后一个元素也是一个局部最小数。
        if (arr[n - 2] > arr[n - 1]) {
            return n - 1;
        }

        int l = 0;
        int r = n - 1;
        // 中间进行二分， 利用数据特性。如果前面两个条件都不满足。说明第一个元素要比第二个元素要大，最后一个元素比倒数第二个要大。说明在第一个
        // 和倒数第一个中间一定存在局部最小值。
        try {
            while (l < r - 1) {
                int midIndex = l + ((r - l) >> 1);
                if (arr[midIndex] < arr[midIndex - 1] && arr[midIndex] < arr[midIndex + 1]) {
                    return midIndex;
                }
                if (arr[midIndex] > arr[midIndex + 1]) {
                    l = midIndex;
                    continue;
                }
                if (arr[midIndex] > arr[midIndex - 1]) {
                    r = midIndex;
                }
            }
        } catch (Exception e) {
            System.err.println(Arrays.toString(arr));
            e.printStackTrace();
        }
        return -1;
    }
}
